package com.chenken;

import com.chenken.AbstractList;

/**
 *	双向链表
 */
public class LinkedList<E> extends AbstractList<E>{
	
	private Node<E> first;
	
	private Node<E> last;
	
	private static final int ELEMENT_NOT_FOUND = -1;

	@Override
	public void clear() {
		first = null;
		last = null;
		size = 0;
	}

	@Override
	public boolean contains(E element) {
		return indexOf(element)>ELEMENT_NOT_FOUND;
	}

	@Override
	public E set(int index, E element) {
		Node<E> node = node(index);
		E old = node.element;
		
		node.element = element;
		return old;
	}

	@Override
	public void add(int index, E element) {
		rangeCheckForAdd(index);
		
		if(index == size) {	//	往最后面添加
			Node<E> oldLast = last;
			last = new Node<E>(element, oldLast, null);
			if(oldLast == null) {	//	是链表添加的第一个元素
				first = last;
			}else {
				oldLast.next = last;
			}
		}else {
			Node<E> next = node(index);
			Node<E> prev = next.prev;
			Node<E> node = new Node<E>(element,prev,next);
			next.prev = node;
			
			if(prev == null) {	//	头结点 index = 0
				first = node;
			}else {
				prev.next = node;
			}
		}
		size++;
	}

	@Override
	public E remove(int index) {
		rangeCheck(index);
		
		Node<E> node = node(index);
		Node<E> prev = node.prev;
		Node<E> next = node.next;
		
		if(prev == null) {	//index == 0
			first = next;
		}else {
			prev.next = next;
		}
		
		if(next == null) {	//index == size-1
			last = prev;
		}else {
			next.prev = prev;
		}
		
		size--;
		return node.element;
	}

	@Override
	public int indexOf(E element) {
		if(element == null) {
			Node<E> node = first;
			for(int i = 0;i<size;i++) {
				if(node.element == null) return i;
				node = node.next;
			}
		}else{
			Node<E> node = first;
			for(int i = 0;i<size;i++) {
				if(element.equals(node.element)) return i;
				node = node.next;
			}
		}
		return ELEMENT_NOT_FOUND;
	}
	
	@Override
	public E get(int index) {
		return node(index).element;
	}
	
	/**
	 *     如果index小于size/2，则从first开始找
	 * 	如果index大于等于size/2，则从last开始找
	 */
	private Node<E> node(int index){
		rangeCheck(index);
		if(index < (size >> 1)) {
			Node<E> node = first;
			for(int i = 0;i<index;i++) {
				node = node.next;
			}
			return node;
		}else {
			Node<E> node = last;
			for(int i = size - 1;i>index;i--) {
				node = node.prev;
			}
			return node;
		}
	}
	
	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("size=").append(size).append(",[");
		Node<E> node = first;
		for(int i = 0;i<size;i++) {
			if(i!=0) {
				stringBuilder.append(",");
			}
			stringBuilder.append(node.element);
			node = node.next;
		}
		stringBuilder.append("]");
		return stringBuilder.toString();
	}




	private static class Node<E>{
		
		E element;
		
		Node<E> prev;
		
		Node<E> next;

		public Node(E element,Node<E> prev, Node<E> next) {
			this.element = element;
			this.prev = prev;
			this.next = next;
		}
	}
	
	
}
